﻿#pragma once
#include "RBTree.h"

namespace bit {
	template <class K, class V>
	class map {
	public:
		struct MapKeyOfT {
			const K& operator() (const pair<K, V>& kv) { return kv.first; }
		};

		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
		iterator begin() { return _t.begin(); }
		iterator end() { return _t.end(); }

		pair<iterator, bool> Insert(const pair<K, V>& kv) { return _t.Insert(kv); }
		//first 和 second 都不可修改
		//pair 对象本身不能被重新赋值。整个对象是只读的
		//但它的 first 和 second 仍然可读（并用于构造新的 pair<const K, V>）。
		//插入时，RBTree 会用 kv.first 和 kv.second 构造一个新的 pair<const K, V>

		V& operator[](const K& key) {
			//insert 返回值规范
			//first: 指向已插入或已存在元素的迭代器
			//second: 是否插入成功（true=新插入，false=已存在）
			pair<iterator, bool> ret = Insert(make_pair(key, V()));
			return ret.first->second;
			//ret.first 是 iterator
			//RBTree的模版参数template <class K, class T, class KeyOfT>
			//map传给 RBTree 的模板参数是：RBTree<K, pair<const K, V>, MapKeyOfT>
			//T = pair<const K, V>
			//RBTreeNode中 T _data，所以 _data = pair<const K, V>
			//迭代器中返回&_node->_data即(pair<const K, V>* )

		}
	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;
	};
}